// 方法一：快排，一个用例超时
var findKthLargest = function (nums, k) {
  const n = nums.length;
  return quickSelect(nums, 0, nums.length - 1, n - k)//第k大元素<=>第n-k小元素
};
// 快速选择函数
function quickSelect(nums, left, right, targetIndex) {
  //如果left、right相等，说明已经找到了目标元素，直接返回该元素
  if (left === right) return nums[left]

  // 随机选一个 pivotIndex
  const randomIndex = left + Math.floor(Math.random() * (right - left + 1));
  // 与 right 交换，使 partition 函数处理一致
  [nums[randomIndex], nums[right]] = [nums[right], nums[randomIndex]];

  //基准索引：分区处理，返回索引right元素（基准元素） 按照 升序排序后的索引（基准索引）
  let pivotIndex = partition(nums, left, right)
  /*如果pivotIndex等于targetIndex，正好返回该索引元素
    如果pivotIndex大于targetIndex，在pivitIndex的左边区间寻找targetIndex；
    如果pivotIndex小于targetIndex，在pivitIndex的右边区间寻找targetIndex */
  if (pivotIndex === targetIndex) {
    return nums[pivotIndex]
  } else if (pivotIndex > targetIndex) {
    return quickSelect(nums, left, pivotIndex - 1, targetIndex) //不要忘了return
  } else {
    return quickSelect(nums, pivotIndex + 1, right, targetIndex) //不要忘了return
  }
}
function partition(nums, left, right) {
  //基准元素：nums[right]
  const pivotValue = nums[right]
  let storeIndex = left
  //遍历i从left到right-1：如果nums[i]小于基准元素pivotValue，交换索引storeIndex和索引i的数组元素，storeIndex++
  //最终storeIndex停留的位置就是基准元素pivotValue的基准索引
  for (let i = left; i < right; i++) {
    if (nums[i] < pivotValue) {
      [nums[storeIndex], nums[i]] = [nums[i], nums[storeIndex]]
      storeIndex++
    }
  }
  //交换索引storeIndex和索引right的数组元素
  [nums[storeIndex], nums[right]] = [nums[right], nums[storeIndex]]
  //返回基准索引
  return storeIndex
}

// 方法二：三路划分 + 快速选择 + 随机基准优化
// var findKthLargest = function (nums, k) {
//   const n = nums.length
//   return quickSelect(nums, 0, n - 1, n - k)//第k大 => 第n-k+1小，排序后索引为n-k
// };
// function quickSelect(nums, left, right, targetIndex) {
//   //区间内只有一个元素，直接返回
//   if (left === right) return nums[left]

//   //在区间[left, right]选择一个随机索引randomIndex
//   const randomIndex = left + Math.floor(Math.random() * (right - left + 1))
//   //交换随机索引randomIndex和索引right的数组元素
//   swap(nums, randomIndex, right)
//   //将索引right的数组元素作为基准值
//   const pivotValue = nums[right]

//   /*
//   小于基准值的区域（索引范围：[left, lt-1]）
//   等于基准值的区域（索引范围：[lt, i-1]）
//   未处理的区域（索引范围：[i, gt]）
//   大于基准值的区域（索引范围：[gt+1, right]）
//   */
//   let lt = left;    // 小于区域的右边界（初始指向left）
//   let i = left;     // 当前遍历位置（初始指向left）
//   let gt = right;   // 大于区域的左边界（初始指向right）
//   //未处理区域非空时循环
//   while (i <= gt) {
//     if (nums[i] < pivotValue) {
//       swap(nums, i, lt)
//       lt++
//       i++ //nums[i]为原来的nums[lt]，属于已处理元素，不需要重新判断，需要i++
//     } else if (nums[i] > pivotValue) {
//       swap(nums, i, gt)
//       gt--
//       /* i++ //nums[i]为原来的nums[gt]，属于未处理元素，需要重新判断，不需要i++ */
//     } else {
//       i++
//     }
//   }

//   //根据targetIndex落在上述不同区间 做出 不同的处理
//   if (targetIndex < lt) {
//     return quickSelect(nums, left, lt - 1, targetIndex)
//   } else if (targetIndex > gt) {
//     return quickSelect(nums, gt + 1, right, targetIndex)
//   } else {
//     return nums[targetIndex]
//   }
// }
// function swap(nums, a, b) {
//   [nums[a], nums[b]] = [nums[b], nums[a]]
// }